【AtCoder】경프전형 039 Tree Distance

스스로 생각해도 몰랐습니다만, 전형적인 문제이므로 해설 AC했습니다. 모든 정점끼리의 최단 경로를 구하려고 하면 TLE가 됩니다. 거기서, 각각의 변을 통과하는 정점의 조합은 몇 가지인가? 생각합니다. 위의 빨간 변의 경우 6 거리. 이 조합을 빠르게 계산하는 것을 고려하면 위와 같이 변 앞과 맞은편으로 그룹을 나누면 좋은 것을 알 수 있습니다. 각각의 그룹으로부터 요소를 하나씩 선택하는 경...

C++AtCoder경기 프로그래밍전형적인 90문